package com.seven.leetcode.problems;

import com.seven.leetcode.utils.TreeNode;

/**
 * 783. 二叉搜索树节点最小距离
 * https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/
 * 级别：Easy
 * <p>
 * 给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
 * <p>
 * 注意：本题与 530：https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/ 相同
 * <p>
 * 示例 1：
 * 输入：root = [4,2,6,1,3]
 * 输出：1
 * <p>
 * 示例 2：
 * 输入：root = [1,0,48,null,null,12,49]
 * 输出：1
 * <p>
 * 提示：
 * 树中节点数目在范围 [2, 100] 内
 * 0 <= Node.val <= 105
 *
 * @author : wenguang
 * @date : 2021/4/02 10:42
 */
public class MinimumDistanceBetweenBstNodes {

    private static TreeNode pre = null;   //pre记录前一节点
    private static int res = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Integer[] nums = new Integer[]{1, 0, 48, null, null, 12, 49};
        TreeNode node = TreeNode.fromArray(nums);
        System.out.println("in: \nnode:" + node);
        int result = minDiffInBST(node);
        System.out.println("out: " + result);
    }

    public static int minDiffInBST(TreeNode root) {
        dfs(root);
        return res;
    }

    private static void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        if (pre != null) {
            res = Math.min(root.val - pre.val, res);   //记录最小
        }
        pre = root;
        dfs(root.right);
    }
}
